package offer.offer04;

import java.util.Deque;
import java.util.LinkedList;

/**
 *
 */
public class S59II队列的最大值 {
    /**
     * 90, 还可以。
     * 维持一个单调队列, 因为可能会出现相等的数, 需要考虑一下, 注意不是单调栈
     */
    private Deque<Integer> max_queue = new LinkedList<>();
    private Deque<Integer> deque = new LinkedList<>();
    public S59II队列的最大值() {

    }

    public int max_value() {
        return max_queue.isEmpty()? -1: max_queue.peek();
    }

    public void push_back(int value) {
        deque.addLast(value);
        while(!max_queue.isEmpty() && max_queue.peekLast() < value)
            max_queue.pollLast();
        max_queue.addLast(value);
    }

    public int pop_front() {
        if(deque.isEmpty()) return -1;
        int front = deque.pop();
        if(front == max_queue.peekFirst())
            max_queue.pollFirst();
        return front;
    }
}
